package com.lw.leetcode.arr.a;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 剑指 Offer 57 - II. 和为s的连续正数序列
 *
 * @author liw
 * @version 1.0
 * @date 2022/7/15 9:51
 */
public class FindContinuousSequence {

    public static void main(String[] args) {
        FindContinuousSequence test = new FindContinuousSequence();

        int n = 9;

        int[][] continuousSequence = test.findContinuousSequence(n);
        for (int[] ints : continuousSequence) {
            System.out.println(Arrays.toString(ints));
        }
    }


    public int[][] findContinuousSequence(int target) {
        if (target < 3) {
            return new int[0][0];
        }
        int length = (target + 3) >> 1;
        int[] arr = new int[length];
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        for (int i = 1; i < length; i++) {
            arr[i] = arr[i - 1] + i;
            map.put(arr[i], i);
        }
        List<int[]> list = new ArrayList<>();
        for (int i = 2; i < length; i++) {
            int t = arr[i] - target;
            if (t < 0 || !map.containsKey(t)) {
                continue;
            }
            int st = map.get(t);
            int[] item = new int[i - st];
            int k = 0;
            for (int j = st + 1; j <= i; j++) {
                item[k++] = j;
            }
            list.add(item);
        }
        int size = list.size();
        int[][] values = new int[size][];
        for (int i = 0; i < size; i++) {
            values[i] = list.get(i);
        }
        return values;
    }

}
